import java.util.Arrays;

/**
 * @author:gao
 * @date:2020/6/14
 * @time:13:22
 * @version:0.0.1
 * @description:none
 */


//1300 前缀和+枚举+折半查找  ，有更优解法
//public class a {
//    class Solution {
//        public int findBestValue(int[] arr, int target) {
//            Arrays.sort(arr);
//            int[] sum = new int[arr.length+1];
//            for(int i=1;i<arr.length;i++){
//                sum[i]=sum[i-1]+arr[i-1]; //前面所有数的和
//            }
//            int ans = 0;
//            int diff = target;
//            for(int i=1;i<=arr[arr.length-1];i++){
//                int index = Arrays.binarySearch(arr,i);
//                if(index<0){
//                    index = - index -1;//不存在，返回插入点index的-index -1
//                }
//                int s = sum[index]+(arr.length-index)*i;
//                int tmp_diff = Math.abs(target-s);
//                if(tmp_diff<diff){
//                    ans = i;
//                    diff=tmp_diff;
//                }
//            }
//            return ans;
//        }
//    }
//}
